/*
 * Copyright (c) 2021
 * User:LENOVO
 * File:反转链表.java
 * Date:2021/02/18 14:19:18
 */

package org.bytedance.链表和数;

import java.util.List;

public class 反转链表 {


    private static class ListNode {
        int value;
        ListNode next;

        public ListNode() {
        }

        public ListNode(int value) {
            this.value = value;
        }
    }


    public static void main(String[] args) {
        ListNode head = new ListNode(3);
        head.next = new ListNode(5);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(4);
        反转链表 instance = new 反转链表();
        ListNode tmp = head;
        ListNode reverse = instance.reverse(tmp);
        printListNode(reverse);
        ListNode res = instance.reverseCursive(reverse);
        printListNode(res);

    }

    private static void printListNode(ListNode head) {
        System.out.println();
        while (head != null) {
            System.out.print(head.value + " ");
            head = head.next;
        }
        System.out.println();
    }

    /**
     * 递归算法
     *
     * @param node
     * @return
     */
    public ListNode reverseCursive(ListNode node) {
        if (node == null || node.next == null) return node;
        ListNode listNode = reverseCursive(node.next);
        //核心逻辑
        node.next.next = node;
        node.next = null;
        return listNode;
    }

    /**
     * 非递归算法
     *
     * @param node
     * @return
     */
    public ListNode reverse(ListNode node) {
        ListNode pre = null, next = null;
        while (node != null) {
          //核心逻辑
          next = node.next;
          node.next = pre;
          pre = node;
          node = next;
        }
        return pre;
    }

}
